#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;



class Solution {
private:
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool dfs(vector<vector<char>>& board, string& s, int i, int j, int pos) {
        if (i < 0 || i >= board.size()) {
            return false;
        }
        if (j < 0 || j >= board[0].size()) {
            return false;
        }
        if (board[i][j] == s[pos]) {
            cout << board[i][j];
            if (pos + 1 == s.length()) {
                return true;
            } else {
                board[i][j] -= 65;
                for (int k = 0; k < 4; k++) {
                    if (dfs(board, s, i + dir[k][0], j + dir[k][1], pos + 1)) {
                        return true;
                    }
                }
                board[i][j] += 65;
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string& word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                cout << i << ", " << j << ": ";
                if (dfs(board, word, i, j, 0)) {
                    cout << endl;
                    return true;
                }
                cout << endl;
            }
        }
        return false;
    }
};

int main() {

    return 0;
}

/**
 * 2022.11.21
 * dfs 模板题
*/